from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        暴力解法，测试会超时！
        :param prices:
        :return:
        """
        if len(prices) < 2:
            return 0
        profit = 0
        for i in range(len(prices)-1):
            for j in range(i+1, len(prices)):
                if prices[j] - prices[i] > profit:
                    profit = prices[j] - prices[i]
        return profit

    def func(self, prices: List[int]) -> int:
        """
        动态规划
        时间复杂度： O(n)
        空间复杂度： O(n)
        :param prices:
        :return:
        """
        if len(prices) < 2:
            return 0
        dp = [0] * len(prices)
        min_price = prices[0]

        for i in range(1, len(prices)):
            min_price = min(min_price, prices[i])
            dp[i] = max(dp[i-1], prices[i]-min_price)
        return dp[-1]

    def func1(self, prices: List[int]) -> int:
        """
        动态规划--空间复杂度优化
        时间复杂度： O(n)
        空间复杂度： O(1)
        :param prices:
        :return:
        """
        if len(prices) < 2:
            return 0
        max_profit = 0
        min_price = prices[0]

        for i in range(1, len(prices)):
            max_profit = max(max_profit, prices[i]-min_price)
            min_price = prices[i] if prices[i] < min_price else min_price
        return max_profit


if __name__ == '__main__':
    x = Solution()
    prices = [7, 1, 5, 3, 6, 4]
    print(x.func1(prices))
